W2. Логическая эквивалентность, нормальные формы (DNF, CNF, ANF)

Автор

Zakhar Podyakov

Дата публикации

17 сентября 2025 г.

Quiz | Flashcards

1. Кратко

1.1 Логические формулы и операторы

В логике формула (formula) (или высказывание) — утверждение, которое можно однозначно считать истинным или ложным. Простые формулы, часто обозначаемые переменными вроде \(p\) или \(q\), можно соединять логическими операторами (logical operators).

  • Отрицание (\(\neg\)): меняет значение на противоположное; \(\neg p\) читается как «не \(p\)».
  • Конъюнкция (\(\land\) или &): логическое «И»; \(p \land q\) истинно только если оба операнда истинны.
  • Дизъюнкция (\(\lor\)): логическое «ИЛИ»; \(p \lor q\) истинно, если хотя бы один из \(p\), \(q\) истинен; ложно только когда оба ложны.
  • Импликация (\(\to\)): «если \(p\), то \(q\)»; \(p \to q\) ложна только при \(p=1\), \(q=0\).
  • Эквиваленция (\(\leftrightarrow\)): «тогда и только тогда»; \(p \leftrightarrow q\) истинна только при одинаковых значениях \(p\) и \(q\).
1.2 Классификация формул

Формулы классифицируют по поведению на всех интерпретациях переменных.

  • Тавтология (tautology): формула всегда истинна. Пример: \(p \lor \neg p\).
  • Противоречие (contradiction): формула всегда ложна. Пример: \(p \land \neg p\).
  • Контингентность (contingency): ни тавтология, ни противоречие; значение зависит от переменных. Пример: \(p \lor q\).
  • Выполнимость (satisfiability): формула выполнима (satisfiable), если существует хотя бы один набор значений переменных, при котором она истинна. Тавтологии и контингентные формулы выполнимы; противоречия — нет. Задача распознавания выполнимости булевых формул — известная задача SAT; теорема Кука–Левина (Cook–Levin theorem) показывает её NP-полноту (NP-complete).
1.3 Логическая эквивалентность (logical equivalence)

Две формулы логически эквивалентны, если их таблицы истинности совпадают; пишут \(\equiv\). Эквивалентности нужны для упрощения и преобразований.

  • Законы тождества (identity laws): \(p \lor F \equiv p\), \(p \land T \equiv p\).
  • Законы доминирования (domination laws): \(p \lor T \equiv T\), \(p \land F \equiv F\).
  • Идемпотентность (idempotent laws): \(p \lor p \equiv p\), \(p \land p \equiv p\).
  • Двойное отрицание (double negation): \(\neg(\neg p) \equiv p\).
  • Коммутативность (commutative laws): \(p \lor q \equiv q \lor p\), \(p \land q \equiv q \land p\).
  • Ассоциативность (associative laws): \((p \lor q) \lor r \equiv p \lor (q \lor r)\), \((p \land q) \land r \equiv p \land (q \land r)\).
  • Дистрибутивность (distributive laws): \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\), \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\).
  • Законы де Моргана (De Morgan’s laws): \(\neg(p \land q) \equiv \neg p \lor \neg q\), \(\neg(p \lor q) \equiv \neg p \land \neg q\).
  • Поглощение (absorption laws): \(p \lor (p \land q) \equiv p\), \(p \land (p \lor q) \equiv p\).
  • Импликация и эквиваленция: \(p \to q \equiv \neg p \lor q\); контрапозиция (contrapositive): \(p \to q \equiv \neg q \to \neg p\); \(p \leftrightarrow q \equiv (p \to q) \land (q \to p)\) и \(p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)\).
1.4 Нормальные формы

Нормальная форма — канонический вид формулы. Часто используют DNF и CNF.

  • DNF: дизъюнкция конъюнктов литералов; литерал (literal) — переменная или её отрицание. Пример: \((p \land q) \lor (\neg p \land r)\). По таблице истинности: строки с 1 → минтермы → дизъюнкция.
  • CNF: конъюнкция дизъюнктов литералов. Пример: \((p \lor q) \land (\neg p \lor r)\). По таблице: строки с 0 → макстермы → конъюнкция.
1.5 Алгебраическая нормальная форма (ANF)

ANF (algebraic normal form), также полином Жегалкина (Zhegalkin polynomial), — представление формулы только через XOR (\(\oplus\)) и AND (\(\cdot\)) с арифметикой по модулю 2 (\(1+1=0\)). В полиноме степени переменных по сути не выше 1, так как \(x \cdot x = x\).

Ключевые подстановки:

  • \(\neg p \equiv p \oplus 1\)
  • \(p \land q \equiv p \cdot q\) (или \(pq\))
  • \(p \lor q \equiv p \oplus q \oplus pq\)
  • \(p \to q \equiv 1 \oplus p \oplus pq\)
  • \(p \leftrightarrow q \equiv 1 \oplus p \oplus q\)

Свойства в \(\mathbb{F}_2\):

  • \(p \oplus p \equiv 0\)
  • \(p \cdot p \equiv p\) (то есть \(p^2 \equiv p\))

2. Определения

  • Тавтология (tautology): формула истинна при любых значениях переменных.
  • Противоречие (contradiction): формула ложна при любых значениях переменных.
  • Контингентность (contingency): формула может быть и истинной, и ложной в зависимости от переменных.
  • Выполнимость (satisfiability): существует набор значений, делающий формулу истинной.
  • Логическая эквивалентность (logical equivalence): совпадение таблиц истинности двух формул.
  • Литерал (literal): переменная или её отрицание.
  • DNF: дизъюнкция одной или нескольких конъюнкций литералов.
  • CNF: конъюнкция одной или нескольких дизъюнкций литералов.
  • ANF: каноническое представление как полином над полем из двух элементов с XOR и AND.

3. Формулы

  • Закон тождества (identity law): \(p \lor 0 \equiv p\)
  • Закон тождества (identity law): \(p \land 1 \equiv p\)
  • Закон дополнения (complement law): \(p \lor \neg p \equiv 1\)
  • Закон дополнения (complement law): \(p \land \neg p \equiv 0\)
  • Идемпотентность (idempotent law): \(p \land p \equiv p\)
  • Идемпотентность (idempotent law): \(p \lor p \equiv p\)
  • Двойное отрицание (double negation law): \(\neg(\neg p) \equiv p\)
  • Ассоциативность (associative law): \((p \lor q) \lor r \equiv p \lor (q \lor r)\)
  • Дистрибутивность (distributive law): \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
  • Дистрибутивность (distributive law): \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)
  • Законы де Моргана (De Morgan’s law): \(\neg(p \land q) \equiv \neg p \lor \neg q\)
  • Законы де Моргана (De Morgan’s law): \(\neg(p \lor q) \equiv \neg p \land \neg q\)
  • Эквивалентность импликации (implication equivalence): \(p \to q \equiv \neg p \lor q\)
  • Эквивалентность эквиваленции (bi-implication equivalence): \(p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)\)
  • Закон смежности (adjacency law): \(p \lor (\neg p \land q) \equiv p \lor q\)
  • Закон упрощения (simplification law): \((p \lor q) \land (p \lor \neg q) \equiv p\)
  • Конъюнкция в ANF: \(p \land q \equiv pq\)
  • Отрицание в ANF: \(\neg p \equiv p \oplus 1\)
  • Дизъюнкция в ANF: \(p \lor q \equiv p \oplus q \oplus pq\)
  • Импликация в ANF: \(p \to q \equiv 1 \oplus p \oplus pq\)
  • Эквиваленция в ANF: \(p \leftrightarrow q \equiv 1 \oplus p \oplus q\)
  • Свойство ANF (идемпотентность умножения): \(p \cdot p \equiv p\)
  • Свойство ANF (XOR с самим собой): \(p \oplus p \equiv 0\)
  • Свойство ANF (нейтральный элемент XOR): \(p \oplus 0 \equiv p\)

4. Примеры

4.1. Доказать тождество (Лаба 2, Задание 1.a)

Докажите, что \(¬¬a ≡ a\).

Показать решение
  1. Таблица: столбцы для \(a\), \(¬a\), \(¬¬a\).
  2. \(¬a\): противоположно \(a\).
  3. \(¬¬a\): противоположно \(¬a\).
  4. Сравнение: столбцы \(a\) и \(¬¬a\) должны совпасть.
a ¬a ¬¬a
0 1 0
1 0 1
Ответ: столбцы \(a\) и \(¬¬a\) совпадают — эквивалентность доказана.
4.2. Доказать тождество (Лаба 2, Задание 1.b)

Докажите, что \(a ↔ b ≡ (a ∧ b) ∨ (¬a ∧ ¬b)\).

Показать решение
  1. Таблица: \(a,b\), левая часть \(a ↔ b\), правая часть с промежуточными столбцами.
  2. Левая часть: \(a ↔ b\) равна 1 только при одинаковых \(a,b\).
  3. Правая часть: вычислите \(a ∧ b\), затем \(¬a ∧ ¬b\), затем их дизъюнкцию.
  4. Сравнение итоговых столбцов:
a b a ↔︎ b a ∧ b ¬a ¬b ¬a ∧ ¬b (a ∧ b) ∨ (¬a ∧ ¬b)
0 0 1 0 1 1 1 1
0 1 0 0 1 0 0 0
1 0 0 0 0 1 0 0
1 1 1 1 0 0 0 1
Ответ: столбцы \(a ↔ b\) и \((a ∧ b) ∨ (¬a ∧ ¬b)\) совпадают.
4.3. Доказать тождество (Лаба 2, Задание 1.c)

Докажите, что \(¬a ∧ (b ∨ ¬c) ≡ (¬a ∧ b) ∨ (¬a ∧ ¬c)\). Это пример дистрибутивного закона (distributive law).

Показать решение
  1. Таблица: \(a,b,c\) и обе стороны эквивалентности.
  2. Левая часть: \(b ∨ ¬c\), затем конъюнкция с \(¬a\).
  3. Правая часть: \(¬a ∧ b\), \(¬a ∧ ¬c\), затем дизъюнкция.
  4. Сравнение итоговых столбцов:
a b c ¬a ¬c b ∨ ¬c ¬a ∧ (b ∨ ¬c) ¬a ∧ b ¬a ∧ ¬c (¬a ∧ b) ∨ (¬a ∧ ¬c)
0 0 0 1 1 1 1 0 1 1
0 0 1 1 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 0 1
1 0 0 0 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0
1 1 0 0 1 1 0 0 0 0
1 1 1 0 0 1 0 0 0 0
Ответ: итоговые столбцы совпадают — дистрибутивность подтверждена.
4.4. Применить отрицание и упростить (Лаба 2, Задание 2)

Возьмите отрицание и упростите по законам де Моргана (De Morgan’s laws) выражение \(¬a ∧ (b ∨ c)\).

Показать решение
  1. Отрицание всей формулы: \(¬(¬a ∧ (b ∨ c))\).
  2. Де Морган для конъюнкции: \(¬(X ∧ Y) ≡ ¬X ∨ ¬Y\) → \(¬(¬a) ∨ ¬(b ∨ c)\).
  3. Двойное отрицание: \(¬(¬a) ≡ a\) → \(a ∨ ¬(b ∨ c)\).
  4. Де Морган для дизъюнкции: \(¬(X ∨ Y) ≡ ¬X ∧ ¬Y\) → \(a ∨ (¬b ∧ ¬c)\).
Ответ: \(a ∨ (¬b ∧ ¬c)\).
4.5. Применить отрицание и упростить (Лаба 2, Задание 2.a)

Возьмите отрицание и упростите (де Морган) для \(¬a ∨ (¬b ∧ c)\).

Показать решение
  1. \(¬(¬a ∨ (¬b ∧ c))\)
  2. \(¬(X ∨ Y) ≡ ¬X ∧ ¬Y\) → \(¬(¬a) ∧ ¬(¬b ∧ c)\)
  3. \(¬(¬a) ≡ a\) → \(a ∧ ¬(¬b ∧ c)\)
  4. \(¬(X ∧ Y) ≡ ¬X ∨ ¬Y\) → \(a ∧ (¬(¬b) ∨ ¬c)\)
  5. \(¬(¬b) ≡ b\) → \(a ∧ (b ∨ ¬c)\)
Ответ: \(a ∧ (b ∨ ¬c)\).
4.6. Применить отрицание и упростить (Лаба 2, Задание 2.b)

Упростите \(¬((¬a ∨ b) ∧ (c ∨ ¬d))\).

Показать решение
  1. \(¬((¬a ∨ b) ∧ (c ∨ ¬d))\)
  2. \(¬(X ∧ Y) ≡ ¬X ∨ ¬Y\) → \(¬(¬a ∨ b) ∨ ¬(c ∨ ¬d)\)
  3. \(¬(X ∨ Y) ≡ ¬X ∧ ¬Y\) → \((¬(¬a) ∧ ¬b) ∨ (¬c ∧ ¬(¬d))\)
  4. Двойные отрицания: \((a ∧ ¬b) ∨ (¬c ∧ d)\).
Ответ: \((a ∧ ¬b) ∨ (¬c ∧ d)\).
4.7. Применить отрицание и упростить (Лаба 2, Задание 2.c)

Упростите \(¬(x₁ ∧ (x₂ ∨ x₃ ∨ (x₄ ∧ x₅)))\).

Показать решение
  1. Внешний де Морган по конъюнкции: \(¬x₁ ∨ ¬(x₂ ∨ x₃ ∨ (x₄ ∧ x₅))\).
  2. Де Морган по дизъюнкции: \(¬x₁ ∨ (¬x₂ ∧ ¬x₃ ∧ ¬(x₄ ∧ x₅))\).
  3. Внутренний де Морган: \(¬x₁ ∨ (¬x₂ ∧ ¬x₃ ∧ (¬x₄ ∨ ¬x₅))\).
Ответ: \(¬x₁ ∨ (¬x₂ ∧ ¬x₃ ∧ (¬x₄ ∨ ¬x₅))\).
4.8. Найти и упростить DNF (Лаба 2, Задание 3)

Найдите DNF по таблице и упростите (дистрибутивность): \(Φ(x, y) ≡ (1110)\).

Показать решение
  1. Таблица и минтермы:
x y Φ(x, y) Минтерм
0 0 1 ¬x ∧ ¬y
0 1 1 ¬x ∧ y
1 0 1 x ∧ ¬y
1 1 0
  1. Полная DNF: \((¬x ∧ ¬y) ∨ (¬x ∧ y) ∨ (x ∧ ¬y)\).
  2. Упрощение: вынесите \(¬x\) из первых двух слагаемых, используйте \(¬y ∨ y ≡ 1\), затем \(A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)\) и \(x ∨ ¬x ≡ 1\).
Ответ: \(¬x ∨ ¬y\).
4.9. Найти и упростить DNF (Лаба 2, Задание 3.a)

Найдите DNF и упростите: \(Φ(x,y,z) ≡ (01111110)\).

Показать решение
  1. Минтермы (строки с 1): \((0,0,1)\), \((0,1,0)\), \((0,1,1)\), \((1,0,0)\), \((1,0,1)\), \((1,1,0)\).
  2. Полная DNF: \((¬x ∧ ¬y ∧ z) ∨ (¬x ∧ y ∧ ¬z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ ¬z)\).
  3. Группировка: сначала неверная «факторизация» отбрасывается; затем проверяются тождества
    • \((¬x ∧ ¬y ∧ z) ∨ (¬x ∧ y ∧ z) = ¬x ∧ z\),
    • \((x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) = x ∧ ¬y\),
    • \((¬x ∧ y ∧ ¬z) ∨ (x ∧ y ∧ ¬z) = y ∧ ¬z\).
  4. Итог: дизъюнкция трёх упрощённых конъюнктов.
Ответ: \((¬x ∧ z) ∨ (x ∧ ¬y) ∨ (y ∧ ¬z)\).
4.10. Найти и упростить CNF (Лаба 2, Задание 4)

Найдите CNF и упростите: \(Ψ(x,y,z) ≡ (00110000)\).

Показать решение
  1. Макстермы (строки с 0): \((x ∨ y ∨ z)\), \((x ∨ y ∨ ¬z)\), \((¬x ∨ y ∨ z)\), \((¬x ∨ y ∨ ¬z)\), \((¬x ∨ ¬y ∨ z)\), \((¬x ∨ ¬y ∨ ¬z)\).
  2. Полная CNF: конъюнкция этих шести дизъюнктов.
  3. Свёртка пар: \((A ∨ B) ∧ (A ∨ ¬B) ≡ A\) даёт \((x ∨ y)\), \((¬x ∨ y)\), \((¬x ∨ ¬y)\).
  4. Дальнейшие преобразования показывают эквивалентность более короткой форме \(¬x ∧ y\) на векторе \((00110000)\); как промежуточный канонический вид удобно оставить \((x ∨ y) ∧ (¬x ∨ y) ∧ (¬x ∨ ¬y)\); дополнительно это упрощается до \(y ∧ (¬x ∨ ¬y)\).
Ответ: \((x ∨ y) ∧ (¬x ∨ y) ∧ (¬x ∨ ¬y)\); далее, например, \(y ∧ (¬x ∨ ¬y)\).
4.11. Найти ANF (Лаба 2, Задание 5.a)

Найдите ANF (algebraic normal form) для \((a → ¬b) ∧ (b → a)\).

Показать решение
  1. Перевод в ANF: \(A → B\) даёт \(1 ⊕ A ⊕ AB\); \(¬B\) даёт \(B ⊕ 1\); отсюда \(a → ¬b\) сводится к \(1 ⊕ ab\), а \(b → a\) к \(1 ⊕ b ⊕ ba\).
  2. Произведение: \((1 ⊕ ab)(1 ⊕ b ⊕ ab)\) (здесь «\(·\)» — AND).
  3. Раскрытие и сокращение по \(X ⊕ X = 0\), \(X·X = X\): получается \(1 ⊕ b\), что эквивалентно \(¬b\).
Ответ: \(1 ⊕ b\) (эквивалентно \(¬b\)).
4.12. Найти ANF (Лаба 2, Задание 5.b)

Найдите ANF для \((¬a ↔ b) → ¬b\).

Показать решение
  1. Внутри: \(¬a ↔ b\) в ANF даёт \(a ⊕ b\); \(¬b\) даёт \(b ⊕ 1\).
  2. Импликация: \(1 ⊕ (a ⊕ b) ⊕ (a ⊕ b)(b ⊕ 1)\).
  3. Раскрытие и приведение по правилам \(\mathbb{F}_2\).
Ответ: \(1 ⊕ b ⊕ ab\).
4.13. Найти ANF (Лаба 2, Задание 5.c)

Найдите ANF для \((b → ¬a) ↔ (a ∨ ¬b)\).

Показать решение
  1. Левая часть (\(b → ¬a\)): сводится к \(1 ⊕ ab\). Правая часть (\(a ∨ ¬b\)): сводится к \(b ⊕ ab ⊕ 1\).
  2. Эквиваленция: \(1 ⊕ (1 ⊕ ab) ⊕ (b ⊕ ab ⊕ 1)\).
  3. Сокращение XOR.
Ответ: \(b ⊕ 1\) (эквивалентно \(¬b\)).
4.14. Найти ANF (Лаба 2, Задание 5.d)

Найдите ANF для \((a → ¬b) ∧ (¬c ∨ ¬a)\).

Показать решение
  1. \(a → ¬b\) даёт \(1 ⊕ ab\); \(¬c ∨ ¬a\) даёт \(ac ⊕ 1\).
  2. Произведение: \((1 ⊕ ab)(1 ⊕ ac)\).
  3. Раскрытие: \(1 ⊕ ac ⊕ ab ⊕ abc\).
Ответ: \(1 ⊕ ab ⊕ ac ⊕ abc\).
4.15. Найти ANF (Лаба 2, Задание 5.e)

Найдите ANF для \((a ∧ ¬c) ↔ (c → ¬b)\).

Показать решение
  1. Левая часть (\(a ∧ ¬c\)): \(ac ⊕ a\). Правая часть (\(c → ¬b\)): \(1 ⊕ cb\).
  2. \(1 ⊕ (ac ⊕ a) ⊕ (1 ⊕ cb)\) → сокращение.
Ответ: \(a ⊕ ac ⊕ bc\).
4.16. Найти ANF (Лаба 2, Задание 5.f)

Найдите ANF для \((¬a → ¬c) ∨ (a ↔ b)\).

Показать решение
  1. Часть 1: \(¬a → ¬c\)
    • \(1 ⊕ (a ⊕ 1) ⊕ (a ⊕ 1)(c ⊕ 1) = 1 ⊕ a ⊕ 1 ⊕ (ac ⊕ a ⊕ c ⊕ 1) = a ⊕ ac ⊕ a ⊕ c ⊕ 1 = ac ⊕ c ⊕ 1\).
  2. Часть 2: \(a ↔ b\)
    • \(1 ⊕ a ⊕ b\).
  3. Дизъюнкция в ANF: \(X ∨ Y ≡ X ⊕ Y ⊕ XY\) при \(X = ac ⊕ c ⊕ 1\), \(Y = 1 ⊕ a ⊕ b\):
    • \((ac ⊕ c ⊕ 1) ⊕ (1 ⊕ a ⊕ b) ⊕ (ac ⊕ c ⊕ 1)(1 ⊕ a ⊕ b)\).
  4. Упрощение произведения:
    • \((ac ⊕ c ⊕ 1)(1 ⊕ a ⊕ b) = c ⊕ bc ⊕ 1 ⊕ a ⊕ b\) (после раскрытия и сокращений).
  5. Сложение с первой частью XOR:
    • \((ac ⊕ c ⊕ a ⊕ b) ⊕ (c ⊕ bc ⊕ 1 ⊕ a ⊕ b) = ac ⊕ bc ⊕ 1\).
Ответ: \(ac ⊕ bc ⊕ 1\).
4.17. Доказать тождество таблицей истинности (Туториал 2, Задание 1)

Докажите, что \(a ∨ 0 ≡ a\).

Показать решение
  1. Столбцы: \(a\), константа \(0\), выражение \(a ∨ 0\).
  2. Две строки по значениям \(a\).
  3. Дизъюнкция с \(0\) не меняет столбец \(a\).
a 0 a ∨ 0
0 0 0
1 0 1
Ответ: столбцы совпадают — тождество верно.
4.18. Доказать тождество таблицей истинности (Туториал 2, Задание 2)

Докажите, что \(a → b ≡ ¬a ∨ b\).

Показать решение
  1. Столбцы: переменные \(a\) и \(b\), выражения \(a → b\) и \(¬a ∨ b\).
  2. Наборы: для двух переменных — четыре комбинации значений.
  3. \(a → b\): ложна только при \(a=1\) и \(b=0\).
  4. \(¬a ∨ b\): сначала вычислите \(¬a\), затем дизъюнкцию с \(b\).
  5. Сравнение: сопоставьте столбцы для \(a → b\) и \(¬a ∨ b\).
a b a → b ¬a ¬a ∨ b
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 1 0 1
Ответ: столбцы \(a → b\) и \(¬a ∨ b\) совпадают.
4.19. Доказать тождество таблицей истинности (Туториал 2, Задание 3)

Докажите, что \(a ∨ (¬a ∧ b) ≡ a ∨ b\).

Показать решение
  1. Столбцы: \(a\), \(b\), промежуточно \(¬a\) и \(¬a ∧ b\), затем обе стороны эквивалентности \(a ∨ (¬a ∧ b)\) и \(a ∨ b\).
  2. Наборы: четыре строки для двух переменных.
  3. Левая часть: вычислите значения \(a ∨ (¬a ∧ b)\).
  4. Правая часть: вычислите значения \(a ∨ b\).
  5. Сравнение: проверьте совпадение итоговых столбцов.
a b ¬a ¬a ∧ b a ∨ (¬a ∧ b) a ∨ b
0 0 1 0 0 0
0 1 1 1 1 1
1 0 0 0 1 1
1 1 0 0 1 1
Ответ: итоговые столбцы совпадают.
4.20. Применить отрицание и упростить (Туториал 2, Задание 4)

Упростите \(¬(¬a ∧ (b ∨ c))\) по законам де Моргана (De Morgan’s laws).

Показать решение
  1. Отрицание всей формулы: \(¬(¬a ∧ (b ∨ c))\).
  2. Де Морган (конъюнкция): \(¬(X ∧ Y) ≡ ¬X ∨ ¬Y\) → \(¬(¬a) ∨ ¬(b ∨ c)\).
  3. Двойное отрицание: \(¬(¬a) ≡ a\) → \(a ∨ ¬(b ∨ c)\).
  4. Де Морган (дизъюнкция): \(¬(X ∨ Y) ≡ ¬X ∧ ¬Y\) → \(a ∨ (¬b ∧ ¬c)\).
Ответ: \(a ∨ (¬b ∧ ¬c)\).
4.21. Применить отрицание и упростить (Туториал 2, Задание 5)

Упростите \(¬(a ∧ (¬b ∨ (c ∧ ¬d)))\) (де Морган).

Показать решение
  1. \(¬(a ∧ (¬b ∨ (c ∧ ¬d)))\)
  2. \(¬(X ∧ Y) ≡ ¬X ∨ ¬Y\) → \(¬a ∨ ¬(¬b ∨ (c ∧ ¬d))\)
  3. \(¬(X ∨ Y) ≡ ¬X ∧ ¬Y\) → \(¬a ∨ (¬(¬b) ∧ ¬(c ∧ ¬d))\)
  4. \(¬(¬b) ≡ b\) → \(¬a ∨ (b ∧ ¬(c ∧ ¬d))\)
  5. \(¬(X ∧ Y) ≡ ¬X ∨ ¬Y\) → \(¬a ∨ (b ∧ (¬c ∨ ¬(¬d)))\)
  6. \(¬(¬d) ≡ d\) → \(¬a ∨ (b ∧ (¬c ∨ d))\)
Ответ: \(¬a ∨ (b ∧ (¬c ∨ d))\).
4.22. Найти и упростить DNF (Туториал 2, Задание 6)

DNF для \(Φ(x,y) ≡ (1110)\) и упрощение.

Показать решение
  1. Таблица: вектор \((1110)\) задаёт столбец значений \(Φ\) при переборе \((x,y)\) в порядке \((0,0),(0,1),(1,0),(1,1)\).
x y Φ(x, y)
0 0 1
0 1 1
1 0 1
1 1 0
  1. DNF: дизъюнкция минтермов по строкам, где \(Φ=1\):
    • строка \((0,0)\): \(¬x ∧ ¬y\);
    • строка \((0,1)\): \(¬x ∧ y\);
    • строка \((1,0)\): \(x ∧ ¬y\);
    • итого \((¬x ∧ ¬y) ∨ (¬x ∧ y) ∨ (x ∧ ¬y)\).
  2. Упрощение: вынесите \(¬x\) из первых двух слагаемых: \(¬x ∧ (¬y ∨ y) ∨ (x ∧ ¬y)\); так как \((¬y ∨ y) ≡ 1\), получается \((¬x ∧ 1) ∨ (x ∧ ¬y)\), то есть \(¬x ∨ (x ∧ ¬y)\); по дистрибутивности \((¬x ∨ x) ∧ (¬x ∨ ¬y)\) и, так как \((¬x ∨ x) ≡ 1\), остаётся \(¬x ∨ ¬y\).
Ответ: \(¬x ∨ ¬y\).
4.23. Доказать тождество (Туториал 2, Задание 7)

Докажите \(x^n ≡ x\) в смысле идемпотентности (idempotence): \(x ∧ x ≡ x\).

Показать решение
  1. Интерпретация: в булевой алгебре «степень» \(x^n\) здесь соответствует повторной конъюнкции \(x ∧ x ∧ \dots ∧ x\), которая по идемпотентности сводится к \(x ∧ x\).
  2. Таблица: столбцы для \(x\) и для \(x ∧ x\).
  3. \(x ∧ x\): равно 1 только когда оба операнда равны 1.
  4. Сравнение: столбцы совпадают.
x x ∧ x
0 0
1 1
Ответ: столбцы совпадают.
4.24. Доказать тождество с XOR (Туториал 2, Задание 8)

Докажите \(x ⊕ x ≡ 0\).

Показать решение
x x ⊕ x
0 0 ⊕ 0 = 0
1 1 ⊕ 1 = 0
Ответ: столбец всегда 0.
4.25. Опровергнуть тождество с XOR (Туториал 2, Задание 9)

Покажите, что \(x ⊕ (y · z) ≠ (x ⊕ y) · (x ⊕ z)\) (оператор «\(·\)» — AND).

Показать решение

Контрпример \(x=1,y=1,z=0\): слева \(1\), справа \(0\).

Ответ: XOR не дистрибутивен относительно AND.
4.26. Найти ANF (Туториал 2, Задание 10)

Найдите ANF выражения \((x^2 ⊕ xy ⊕ 1) ⊕ (x^2y ⊕ xy^2 ⊕ x ⊕ y ⊕ 1)\).

Показать решение

Используйте идемпотентность \(x^2=x\), \(y^2=y\) и правила XOR.

Ответ: \(xy ⊕ y\).
4.27. Найти ANF (Туториал 2, Задание 11)

Найдите ANF для \((a ∧ ¬b) → ¬a\).

Показать решение

Сначала импликация и де Морган дают \(¬a ∨ b\), затем перевод дизъюнкции в ANF.

Ответ: \(a ⊕ ab ⊕ 1\).
4.28. Найти ANF (Туториал 2, Задание 12)

Найдите ANF для \((¬a ∧ b) ∨ (a ∧ b)\).

Показать решение

Вынесите \(b\): \((¬a ∨ a) ∧ b ≡ b\).

Ответ: \(b\).